1. Field of the Invention
The present invention generally relates to computer networks. More particularly, the invention relates to electronic switches through which communications pass from one point in a network to another. Still more particularly, the invention relates to load balancing in a switch-based fabric.
2. Background Information
Initially, computers were most typically used in a standalone manner. It is now commonplace for computers and other types of computer-related and electronic devices to communicate with each other over a network. The ability for computers to communicate with one another has lead to the creation of networks ranging from small networks comprising two or three computers to vast networks comprising hundreds or even thousands of computers. Networks can be set up to provide a wide assortment of capabilities. For example, networks of computers may permit each computer to share a centralized mass storage device or printer. Further, networks enable electronic mail and numerous other types of services. Generally, a network's infrastructure comprises switches, routers, hubs and the like to coordinate the effective and efficient transfer of data and commands from one point on the network to another.
Networks often comprise a “fabric” of interconnected switches which are devices that route data packets from a source port to a destination port. FIG. 1 exemplifies a switch fabric having five switches 20, 22, 24, 26, and 28. The switches 20-28 are interconnected by links 30-38, as shown. One or more end node devices can be connected to one or more of the switches. In FIG. 1, four end node devices 40, 42, 44 and 46 are connected to switch 20 and two end node devices 48 and 50 connect to switch 24. The devices 40-50 may be of any desirable type of device. For example, devices 40, 42 and 50 comprise network storage devices and devices 44, 46 and 48 comprise servers.
An end node device 40-46 connected to switch 20 may need to send a data packet to an end node device 48, 50 connected to switch 24. The packet can be routed from switch 20 to switch 24 via one of two paths in the exemplary architecture of FIG. 1. One path comprises switches 20-22-24 and the other path comprises switches 20-28-26-24. In many networks, the path that will be used between pairs of switches is determined a priori during system initialization or when the fabric configuration changes such as the addition or removal of a switch. Various path selection algorithms have been suggested and used. One such conventional path selection algorithm is often referred to as the “shortest path” algorithm. According to this algorithm, the shortest path is selected to be the path for routing packets between switches. The shortest path takes into account the bandwidth of the various links interconnecting the switches.
Referring still to FIG. 1, a “cost” value is assigned to each link. The numbers shown in parentheses adjacent each link represents the cost of each link. The cost values are generally arbitrary in magnitude, but typically correlate with the inverse of the bandwidth of the links. That is, higher bandwidth links have lower costs and lower bandwidth links have higher costs. For example, links 30 and 32 may have the same bandwidth of 1 gigabits per second (“gbps”) and, as such, may be assigned a cost value of 1000. Links 34, 36, and 38 may have twice the bandwidth of links 30 and 32 (2 gbps) and accordingly may be assigned cost values of 500 (one-half of the cost of links 30 and 32). The shortest path between switches 20 and 24 represents the path with the lowest total cost. The total cost of a path is the sum of the costs associated with the links comprising the path. In the example of FIG. 1, the path comprising switches 20-22-24 has a total cost of 2000, while the total cost of the 20-28-26-24 path is 1500. As the lowest cost path, the 20-28-26-24 path will be selected to be the path used for routing data packets between end node devices 40-46 and 48-50.
When computing the lowest cost path between a pair of switches (e.g., switches 20 and 24), it may be that two or more paths have the lowest, yet equal, cost. In this situation, a load balancing technique is employed to determine how to balance the traffic loads between the various lowest cost paths. For example, in FIG. 2 three paths exist between switches 60 and 70. Path A includes switches 60-62-68-70, while paths B and C include switches 60-66-74-76-70 and 60-66-64-72-74-76-70, respectively. The cost of paths A and B is 3000 while the cost of path C is 5500. Thus, paths A and B are selected as the lowest cost paths and the network traffic from switch 60 destined for switch 70 is balanced between those two paths.
One load balancing technique that has been used is to distribute end node devices among the various lowest cost paths based on the rated bandwidths of the links connecting the end nodes to their associated switches. Such links are referred to as “peripheral links” for purposes of this disclosure and are identified in FIG. 2 with the reference numeral 43. For example, peripheral links 43 in FIG. 2 may all be 2 gbps links and thus the four end node devices 40-46 will be distributed evenly between the two lowest cost paths A and B with two of the end node devices connected to switch 60 assigned to path A and the other two end node devices assigned to path B.
Although current load balancing schemes, such as that described above, generally work well, there is always room for improvement to make a network operate more efficiently. Accordingly, any improvement in load balancing schemes is highly desirable.